package com.samxcode.leetcode;

/**
 * Implement next permutation, which rearranges numbers into the lexicographically next greater
 * permutation of numbers.
 * 
 * If such arrangement is not possible, it must rearrange it as the lowest possible order (ie,
 * sorted in ascending order).
 * 
 * The replacement must be in-place, do not allocate extra memory.
 * 
 * @author Sam
 *
 */
public class NextPermutation {
    
    public static void main(String[] args) {
        int[] nums = {2, 1, 3};
        nextPermutation(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.println(nums[i]);
        }
    }

    public static void nextPermutation(int[] nums) {
        if (nums.length <= 1)
            return;
        //find the number which is larger than the previous
        int i = nums.length - 1;
        for (; i > 0; i--) {
            if (nums[i - 1] < nums[i]) {
                break;
            }
        }
        //find the number which is larger than the special number from the end of nums, swap them
        if (i != 0) {
            for (int j = nums.length - 1; j > i - 1; j--) {
                if (nums[j] > nums[i - 1]) {
                    int temp = nums[i - 1];
                    nums[i - 1] = nums[j];
                    nums[j] = temp;
                    break;
                }
            }
        }
        //reverse
        for (int left = i, right = nums.length - 1; left < right ; left++, right--) {
//            nums[left] = nums[left] ^ nums[right];
//            nums[right] = nums[left] ^ nums[right];
//            nums[left] = nums[left] ^ nums[right];
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }
    }
}
